//请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，
// 但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
* 二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串
* 从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改
* 序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
* */
public class Solution {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

    }
    public int index = 0;
    public void SerializeFunction(TreeNode root, StringBuilder str){
        if(root == null){
            str.append("#");
            return;
        }
        str.append(root.val).append('!');
        SerializeFunction(root.left,str);
        SerializeFunction(root.right,str);
    }
    public String Serialize(TreeNode root) {
        if(root == null){
            return "#";
        }
        StringBuilder res = new StringBuilder();
        SerializeFunction(root,res);
        return res.toString();
    }
    public TreeNode DeserializeFunction(String str) {
        if(str.charAt(index) == '#'){
            index++;
            return null;
        }
        int val = 0;
        while(str.charAt(index) !='!' &&index != str.length()){
            val = val*10+((str.charAt(index)-'0'));
            index++;
        }
        TreeNode root = new TreeNode(val);
        if(index == str.length()){
            return root;
        }else{
            index++;
        }
        root.left = DeserializeFunction(str);
        root.right = DeserializeFunction(str);
        return root;
    }
    public TreeNode Deserialize(String str){
        if(str == "#"){
            return null;
        }
        TreeNode res = DeserializeFunction(str);
        return res;
    }
}
